package cn.mayday.algorithms.offer.day20200920;

/**
 * @description: 剑指 Offer 16. 数值的整数次方 ，难度中等
 * @author: mayday
 * @date: 2020/9/20 9:15
 * @version: 1.0
 */
public class Arrow20MyPow {


    public static void main(String[] args) {
        System.out.println(new Arrow20MyPow().myPow(5, 3));

        System.out.println(new Arrow20MyPow().myPow(2, -2));

    }

    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
//            return myPow(1 / x, -n); // 数组越界，提取一个1/x
            return 1 / x * myPow(1 / x, -n - 1);
        } else {
            // 如果为偶数，二分减半
            if (n % 2 == 0) {
                return myPow(x * x, n / 2);
            } else {
                // 如果为奇数，提取一个，继续偶数
                return x * myPow(x * x, n / 2);
            }
        }
    }
}
